#include <stdio.h>

int fibonacci_fast(int n) {
    int a = n % 2;
    int b = 1;

	for (int i = 0; i < n/2; i++ ){
		a += b;
		b += a;
	}

	return a;
}

int fibonacci_fast_(int n) {
    if (n <= 1){
        return n;
    }
    
    if (n == 2){
        return 1;
    }
    
    int a[n+1];
    a[0]=0;
    a[1]=1;
    a[2]=1;

    for(int i=2; i <= n; i++) {
        a[i] = a[i-1] + a[i-2];
    }

    return a[n];
}
